Search results for "Constraint satisfaction"

Une structure o-minimale sans décomposition cellulaire

2008

Resume Nous construisons une extension o-minimale du corps des nombres reels qui n'admet pas la propriete de decomposition cellulaire en classe C ∞ . Pour citer cet article : O. Le Gal, J.-P. Rolin, C. R. Acad. Sci. Paris, Ser. I 346 (2008).

A decomposition approach to dual shuttle automated storage and retrieval systems

2016

[EN] Automated Storage and Retrieval Systems (AS/RS) have become vital in today¿s distribution and production environments, however it remains necessary to equip them with more efficient operational control policies. Motivated by real situations encountered by companies employing AS/RS, the present paper studies a miniload AS/RS system, with a dual shuttle crane in which a set of storage and retrieval requests must be scheduled such that the prioritized waiting time is minimized. Dual shuttle cranes have received minimal academic attention and thus continue to pose new problems that must be solved. The miniload AS/RS problem is addressed by decomposing it into a location assignment and sequ…

Decomposition and Mean-Field Approach to Mixed Integer Optimal Compensation Problems

2016

Mixed integer optimal compensation deals with optimization problems with integer- and real-valued control variables to compensate disturbances in dynamic systems. The mixed integer nature of controls could lead to intractability in problems of large dimensions. To address this challenge, we introduce a decomposition method which turns the original n-dimensional optimization problem into n independent scalar problems of lot sizing form. Each of these problems can be viewed as a two-player zero-sum game, which introduces some element of conservatism. Each scalar problem is then reformulated as a shortest path one and solved through linear programming over a receding horizon, a step that mirro…

Improving Interpolants for Linear Arithmetic

2015

Craig interpolation for satisfiability modulo theory formulas have come more into focus for applications of formal verification. In this paper we, introduce a method to reduce the size of linear constraints used in the description of already computed interpolant in the theory of linear arithmetic with respect to the number of linear constraints. We successfully improve interpolants by combining satisfiability modulo theory and linear programming in a local search heuristic. Our experimental results suggest a lower running time and a larger reduction compared to other methods from the literature.

On embedding Boolean as a subtype of integer

1990

Counting by Statistics on Search Trees: Application to Constraint Satisfaction Problems

1997

In 1975, Knuth proposed a simple statistical method for investigating search trees. We use this technique for estimating the number of solutions of constraint satisfaction problem CSP and boolean satisfiability problem SAT instances. We show that, depending on domain reductions, tree-based estimates have a lower variance than estimates based on uniform sampling from the search space. Nevertheless, because the variance remains extremely high in the general case, a confidence interval cannot be derived, but a lower bound of the number of solutions. These results are confirmed by many experiments.

Constraint qualifications and Lagrange multipliers in nondifferentiable programming problems

1994

In this paper, we present several constraint qualifications, and we show that these conditions guarantee the nonvacuity and the boundedness of the Lagrange multiplier sets for general nondifferentiable programming problems. The relationships with various constraint qualifications are investigated.

Exact and Approximate Algorithms for Two–Criteria Topological Design Problem of WAN with Budget and Delay Constraints

2004

This paper studies the problem of designing wide area networks (WAN). In the paper the two-criteria topology assignment problem with two constraints is considered. The goal is select flow routes, channel capacities and network topology in order to minimize the total average delay per packet and the leasing cost of channels subject to the budget constraint and delay constraint. The problem is NP-complete. Then, the branch and bound method is used to construct the exact algorithm. Also the approximate algorithm is presented. Some computational results are reported. Based on computational experiments, several properties of the considered problem are formulated.

Decision Support Systems Based on CLP Approach in SMEs

2006

The paper focuses on a selected class of decision problems related with the production flow planning in SMEs, particularly in new production orders. Verification of orders gives a possibility to evaluate whether resources capacity of a manufacturer is balanced with the orderer's requirements. The class of decision problems under analysis is included in the scope of organizational production preparation and can be naturally determined by available CLP (Constraint Logic Programming) tools. The approach proposed in the paper is based on establishment of an interface which facilitates its task oriented use. The system has been presented on the basis of a sample order execution in a manufacturer…

Guaranteed tuning of PID controllers for parametric uncertain systems

2004

This paper presents a methodology for tuning the controller of a parametric uncertain plant in order to guarantee the satisfaction of specifications. These specifications are defined by means of an interval reference model that represents the set of satisfactory time or frequency behaviors. The controller synthesis is then formulated as a set-inclusion problem in the frequency domain. Interval techniques for the solution of constraint satisfaction problems are applied to design fixed-structure controllers in a guaranteed manner. In particular, PID controllers are considered since they are widely used in industry.